package main.leetcode.clockin.Auguest;

import java.util.ArrayList;
import java.util.List;

/**
 * 491. 递增子序列
 *
 * <p>给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
 *
 * <p>示例: 输入: [4, 6, 7, 7] 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7],
 * [4,7,7]]
 *
 * <p>说明: 给定数组的长度不会超过15。 数组中的整数范围是 [-100,100]。 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
 *
 * <p>ps：题目要求的是按照当前数组顺序中的递增数列，而不是要其中的所有递增序列，也即意味着无需对其做预排序
 */
public class day25 {
    private List<List<Integer>> res;

    public static void main(String[] args) {
        System.out.println(new day25().findSubsequences(new int[] {4, 6, 7, 7}));
    }

    public List<List<Integer>> findSubsequences(int[] nums) {
        res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        dfs(nums, 0, Integer.MIN_VALUE, new ArrayList<>());
        return res;
    }

    private void dfs(int[] nums, int i, int pre, List<Integer> cur) {
        if (i == nums.length) {
            if (cur.size() > 1) {
                res.add(new ArrayList<>(cur));
            }
            return;
        }
        if (nums[i] >= pre) {
            cur.add(nums[i]);
            dfs(nums, i + 1, nums[i], cur);
            cur.remove(cur.size() - 1);
        }
        // 不相等，可以跳过当前的数，去重
        if (nums[i] != pre) {
            dfs(nums, i + 1, pre, cur);
        }
    }
}
